package com.chilly.other;

import java.util.*;

/**
 * Created by Chilly Cui on 2020/11/24.
 */
public class Demo {
    public static void main(String[] args) {
//        LinkedList<Integer> linkedList = new LinkedList<>();

//        linkedList.addFirst(1);
//        linkedList.add(2);
//
//        linkedList.addFirst(0);
//        linkedList.forEach(System.out::println);
//        linkedList.removeFirst();
//        linkedList.removeLast();
//        linkedList.addLast(3);
//        linkedList.addLast(4);
//        linkedList.addLast(5);

//        System.out.println(linkedList.getLast());
//        System.out.println(linkedList.getFirst());
//        linkedList.addFirst(1);
//        linkedList.addFirst(2);
//        linkedList.addFirst(3);

//        linkedList.add(1);
//        linkedList.add(2);
//        linkedList.add(3);
//        linkedList.forEach(System.out::println);

//        LinkedList<String> ll = new LinkedList<>();
//        ll.add("cdcd");
//        ll.add("e");
//        ll.add("f");
//        System.out.println(ll);
//        Collections.reverse(ll);
//        System.out.println(ll);
//
//        StringBuffer sb = new StringBuffer();
//        sb.append("cdcd");
//        sb.append("e");
//        sb.append("f");
//        System.out.println(sb);
//        System.out.println(sb.reverse());

//        Map<String,String> map = new HashMap<>();
//        for (int i = 0; i < 20; i++) {
//            map.put(i+"k",i+"v");
//            System.out.println(i);
//        }

//        int i = 1;
//        int j = 0;
//
//        System.out.println(j=i);
//        if ((j=i) == 2){
//            System.out.println(true);
//        }
//        System.out.println(j);

        System.out.println(MoreThanHalfNum_Solution(new int[]{1, 3, 2, 5, 2, 2, 2, 4, 2}));
    }

    //数组中超过一半的数字
    //候选人法
    public static int MoreThanHalfNum_Solution(int[] array) {
        int cond = -1; //候选人cond = -1
        int cnt = 0;
        for (int i = 0; i < array.length; i++) {
            if (cnt == 0) {//如果cnt=0， 表示没有候选人
                cond = array[i];
                ++cnt;
            } else { //如果cnt > 0, 表示有候选人，如果当前数=cond，则++cnt
                if (array[i] == cond) {
                    System.out.println(cond);
                    ++cnt;
                } else {
                    --cnt;//否则--cnt
                }
            }
        }

        cnt = 0;
        for (int k : array) {
            if (cond == k) ++cnt;
        }
        if (cnt > array.length / 2) return cond;
        return 0;
    }

    public static int MoreThanHalfNum_Solution1(int[] array) {
        int len = array.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < len; i++) {
            int k = array[i];
            if (map.containsKey(k)) {
                map.put(k, map.get(k) + 1);
            } else {
                map.put(k, 1);
            }
        }

        Iterator<Integer> it = map.keySet().iterator();
        while (it.hasNext()) {
            Integer k = it.next();
            if (map.get(k) > len / 2) {
                return k;
            }
        }
        return 0;
    }
}
